# 走方格
# 2025/3/26
import heapq


def shortest_time(matrix):
    """
    使用Dijkstra算法计算单源最短路径

    参数:
        matrix: 一个nxn的矩阵

    返回:
        从矩阵(0,0)到(n-1,n-1)的最短距离
    """
    INF = float('inf')
    n = len(matrix)
    dist = [[INF] * n for _ in range(n)]
    dist[0][0] = 0
    heap = [(0.0, 0, 0)]  # 起始节点(路径长度, r, c)
    while heap:
        path_len, row, col = heapq.heappop(heap)  # 弹出当前路径长度最小的元素
        if path_len > dist[row][col]:
            continue  # 已存在更优的路径

        if row == n - 1 and col == n - 1:
            return path_len

        if row < n - 1:  # 向下移动一格
            if dist[row + 1][col] > dist[row][col] + 1:
                dist[row + 1][col] = dist[row][col] + 1
                heapq.heappush(heap, (dist[row + 1][col], row + 1, col))

        if col < n - 1:  # 向右移动一格
            if dist[row][col + 1] > dist[row][col] + 1:
                dist[row][col + 1] = dist[row][col] + 1
                heapq.heappush(heap, (dist[row][col + 1], row, col + 1))

        c = col  # 向右移动L格
        while c < n - 1 and matrix[row][c + 1] < matrix[row][c]:
            c += 1
        if dist[row][c] > dist[row][col] + 1:
            dist[row][c] = dist[row][col] + 1
            heapq.heappush(heap, (dist[row][c], row, c))

        c = col  # 向左移动L格
        while c > 0 and matrix[row][c - 1] < matrix[row][c]:
            c -= 1
        if dist[row][c] > dist[row][col] + 1:
            dist[row][c] = dist[row][col] + 1
            heapq.heappush(heap, (dist[row][c], row, c))

    return dist[n - 1][n - 1]


if __name__ == '__main__':
    matrix = [[0, 1, 9, 3],
              [2, 9, 3, 7],
              [8, 4, 8, 9],
              [9, 8, 0, 7]]
    print(shortest_time(matrix))  # 5
    matrix = [[38, 68, 68, 36, 50, 74, 62, 13, 62, 25],
              [89, 84, 40, 86, 69, 56, 68, 15, 63, 60],
              [6, 36, 19, 94, 83, 88, 19, 33, 45, 96],
              [98, 99, 75, 74, 37, 10, 44, 69, 61, 70],
              [99, 9, 67, 25, 15, 37, 44, 16, 92, 79],
              [93, 14, 17, 2, 29, 27, 55, 39, 71, 6],
              [12, 88, 29, 59, 26, 69, 86, 69, 64, 37],
              [35, 77, 15, 75, 89, 64, 97, 49, 97, 57],
              [28, 25, 51, 68, 31, 8, 47, 88, 2, 9],
              [92, 5, 25, 39, 83, 56, 83, 93, 56, 90]]
    print(shortest_time(matrix))  # 13
